package com.foxzzz.binary.search;

// c
public class Solution878 {
    public static long[] getNum(long num, long a, long b) {
        long[] result = new long[2];
        //结果要减去公倍数
        result[0] = num / a + num / b - num /(a * b);

        result[1] = num / a * a > num / b * b ? num / a * a : num / b * b;
        return result;
    }

    public static long maxCommonFactor(long A, long B) {
        long min = A > B ? B : A;
        long max = A > B ? A : B;
        long temp = -1;
        while (temp != 0) {
            temp = max % min;
            max = min;
            min = temp;
        }
        return max;
    }
    public int nthMagicalNumber(int N, int A, int B) {
        long min = A > B ? B : A;
        long max = A > B ? A : B;
        long factor = maxCommonFactor(A, B);
        min = min / factor;
        max = max / factor;
        if (min == 1)
            return (int)(((long)N * min * factor )%1000000007);
        long high = max * N;
        long low = 0;
        while (low <= high) {
            long mid = (low + high) >> 1;
            long[] ret = getNum(mid, min, max);
            if (ret[0] == N)
                return (int)((ret[1]*factor)%1000000007);
            else if (ret[0] < N)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return -1;
    }

    public static void main(String[] args) {


        System.out.println(new Solution878().nthMagicalNumber(1000000000, 39999, 40000));

    }


}
